Although Code Division Multiple Access (CDMA) or spread spectrum communications has been around for many years, there is an increasing interest in using spread spectrum systems in commercial applications to allow superior quality performance and a greater number of users within a given bandwidth. The digital format of CDMA architecture allows complex processing and high-level algorithms for transmission and reception.
In a CDMA system, each signal is transmitted using spread spectrum techniques. The transmitted informational data stream is impressed upon a much higher rate data stream termed a signature sequence. The bit stream of the signature sequence data is typically binary, and can be generated using a pseudo-noise (PN) process that appears random, but can be replicated by an authorized receiver. The informational data stream and the high bit rate signature sequence stream are combined by multiplying the two bit streams together, assuming the binary values of the two bit streams are represented by +1 or −1. This combination of the higher bit rate signal with the lower bit rate data stream is called spreading the informational data stream signal. Each informational data stream or channel is allocated a unique signature sequence.
In the operation of standard single-user receivers, a plurality of spread information signals each modulate a radio frequency (RF) carrier and may be jointly received as a composite signal at the single receiver. Each of the spread signals overlaps all of the other spread signals, as well as noise-related signals, in both frequency and time. The receiver correlates the composite signal with one of the unique time, frequency, or code sequences, and the corresponding information signal is isolated and processed. This is generally termed matched filtering. The FDMA, TDMA, or CDMA signals have been designed to separate in this fashion, and the desired information is retrieved.
In joint detection signal processing, the waveform appearing at the receiver is not processed by standard single-user processing, or a combination of several single-user processors. The joint detection processing more commonly referred to as Multiuser Detection (MUD), proceeds by computing the outputs for each user in one mathematical step, wherein data from each user is simultaneously considered. In the previous example for the single-user receiver, MUD is employed by replacing the matched filter with a decorrelator. In the operation of a decorrelator, the matched filter taps for each user is collected into a signature matrix (one column for each user), sometimes called the ‘S’ matrix. The decorrelator would jointly compute the K bits {right arrow over (b)}=(SHS)−1SHr, where r is the received data. This can be contrasted with the matched filters that would individually compute the single bit values (for each user k) bk=(skHsk)−1skHr, where sk is the matched filter for the kth user.
There has been considerable research to address joint demodulation, which is further described in S. Verdu, “Minimum Probability of Error For Asynchronous Gaussian Multiple-Access Channels,” IEEE Trans. Info. Theory, Vol. IT-32, pp. 85-96, R. Lupas and S. Verdu, “Linear multiuser detectors for synchronous code-division multiple-access channels,” IEEE Trans. Inform. Theory, Vol. 35, pp. 123-136, January 1989; and R. Lupas and S. Verdu, “Near-far resistance of multiuser detectors in asynchronous channels,” IEEE Trans. Commun., Vol. 38, pp. 496-508, April 1990. A description of CDMA communication techniques is further outlined in U.S. Pat. No. 5,506,861, which describes radiotelephone communication systems, and in particular, receivers for jointly demodulating a plurality of CDMA signals with multipath time dispersion.
There are a host of approaches for jointly demodulating any set of interfering digitally modulated signals. Maximum Likelihood Sequence Estimation determines the most likely set of transmitted information bits for a plurality of digital signals without multipath time dispersion. The maximum likelihood joint demodulator is capable, in theory, of accommodating the largest number of interfering signals, but has a prohibitive computational complexity that makes it commercially impractical. The decorrelation receiver is another, less computationally complex receiver processing approach that zeroes out the interfering signals, or decorrelates the different signals. The decorrelator, as well as virtually every other lower complexity joint demodulator, is generally non-operational when the number of signals is over a set threshold which falls significantly short of the theoretical maximum.
There are various multiuser detectors known in the art, including optimal or maximum likelihood MUD, maximum likelihood sequence estimator for multiple interfering users, successive interference cancellation, TurboMUD or iterative MUD, and various linear algebra based multi-user detectors such as those detailed in the well-known text “Multiuser Detection” by Sergio Verdu. In basic terms, turbo-decoding refers to iteratively passing information in the form of temporary or provisional bit decisions between a MUD processing block, and a decoding processing block, wherein for a turbo MUD the data is coded at the source.
The Viterbi algorithm is a method for decoding convolutional codes, and is a maximum-likelihood decoding method that minimizes the sequence-error probability for convolutional codes. To minimize the symbol-error probability, Bahl, Cocke, Jelinek, and Raviv (BCJR) published a forward-backward a posteriori probability (APP) decoding algorithm, the BCJR algorithm. The BCJR algorithm has seen an increased activity in coding field in relation to turbo decoding because it computes and stores likelihoods at each step, and can therefore provides more precise information to the MUD.
A MUD algorithm within the TurboMUD system determines discrete estimates of the transmitted channel symbols, with the estimates then provided to a bank of single-user decoders (one decoder for each user) to recover the input bit streams of all transmitted signals. Two general types of multi-user detectors within the TurboMUD system are possible, namely those that provide hard outputs, which are discrete values, and those that provide soft outputs, which indicate both the discrete estimate and the probability that the estimate is correct.
A further description of a TurboMUD system is described in an article by Paul D. Alexander, Mark C. Reed, John A. Asenstorfer and Christian B. Schlagel in IEEE Transactions on Communications, vol. 47, number 7, July 1999, entitled “Iterative Multi-User Interference Reduction: Turbo CDMA”, wherein multiple users transmit coded information on the same frequency at the same time.
In a Turbo MUD system, decoding and confidence information is passed between the multiuser detector and decoder components. Maximum a posteriori (MAP) decoders or approximations of MAP decoders are well known to those in the art and are used for both the MUD and single user (SU) decoders so that soft output information is available if desired. The filtered signal is typically then passed into a MUD detector. In the optimal case, the MUD detector is a full-complexity MAP detector. Suboptimal reduced complexity MAP-based approaches are known in the relevant art.
In the state of the art, the MUD detector passes soft decisions in the form of reliability, or confidence, measures to the single user decoders. The reliability measures are presented with one associated with each symbol of each user to the bank of decoders. If the signals were transmitted with interleaving, the reliability measures from the MUD are first passed through a deinterleaver and passed on in shuffled form to the decoder. Shuffling refers to same values but changes the placement or presentation of the values.
MAP decoding is known in the art and further described in C. Schlegel, Trellis Coding, IEEE Press, 1997; Robertson, Villebrun and Hoeher, “A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operation in the Log Domain,” ICC95; Hagenauer, and Hoeher, “A Viterbi Algorithm with Soft-Decision Outputs and its Applications,” Globecom 89; Pottie and Taylor, “A Comparison of Reduced complexity Decoding Algorithms for Trellis Codes,” J Sel. Areas in Comm December 1989. The iterative turbo principle, on which Turbo MUD is based, is described by Berrou, Glavieux, and Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes (1),” ICC 93; Berrou and Glavieux, “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”, Trans on Comm, October 1996; and Wang and Kobayashi, “Low-Complexity MAP Decoding for Turbo Codes”, Vehicular Technology Conference 2000]. Turbo MUD approaches are described in, for example, Alexander, Reed, Asenstorfer, and Schlegel, “Iterative Multiuser Interference Reduction: Turbo CDMA,” Trans on Comm, July 1999; Poor, “Turbo Multiuser Detection: An Overview, ” ISSSTA 2000; and Wang and Poor, “Iterative (Turbo) Soft Interference Cancellation and Decoding for Coded CDMA”, Trans on Comm, July 1999.
Any of the known MUD algorithms can be used as the MUD processing block in a turbo MUD algorithm. The turbo MUD generally outperforms a simple MUD/decode processor because the processing blocks in the turbo configuration are allowed to share information in the form of the provisional bit decisions, rather than each processor operating autonomously. The MUD algorithm within a Turbo MUD system computes estimates of the transmitted channel symbols and passes them to a bank of single-user decoders (one decoder for each user). This process proceeds for several iterations, eventually recovering the input bit streams of all transmitted signals.
For these reasons, to achieve real-time performance by reducing the computational complexity of an iterative multi-user, the state of the art suggests linear algorithms for the MUD processing block rather than optimal MUD or the T and M algorithm counterparts. It is well known that the reduction in performance of the linear MUDs can be offset by the gains due to the iteration in the turbo MUD. For example, it is not uncommon that five iterations in a turbo MUD between a linear MUD and a decoder can obtain optimal MUD like performance with fewer computations, even though the processing is repeated five times.
Higher complexity algorithms such as M-algorithm, T-algorithm, FANO or reduced state Viterbi consume more processing time, but produce a more accurate decisions tree. Lower complexity linear MUD algorithms consume less processing time but may not be as accurate. It should be understood that the present invention, as described herein, can use any tree pruned search for the MUD in order to perform suboptimal searching to tree prune without having to do every search. It should also be apparent to those skilled in the art that any higher order tree pruned search such as FANO, M-algorithm, T-algorithm or reduced state Viterbi can be used for the MUD processing.
The MUD outputs a bit (or symbol) stream to a bank of error correcting decoders. In one embodiment of this invention, the decoders provide soft output streams of values associated with the bit streams of each interfering user's signal present in the received signal. MUD can employ any of the soft decision input soft decision output multiuser detector such as a linear-based soft decision MUD known in the art such as Chan and Wornell, ‘A Class of Asymptotically Optimum Iterated-Decision Multiuser Detectors’, and Wang and Poor, ‘Iterative (Turbo) Soft Interference Cancellation and Decoding for Coded CDMA’, IEEE Trans. on Comms, July 1999, and Moher, “An Iterative Multiuser Decoder for Near Capacity Communication,” IEEE Trans. on Comms., v46, n7, July 1998. The system can also provide hard decisions with the MUD and bank of decoders described in the art for a reduced multi-access interference linear multiuser detector and hard decision error correction decoder.
The growing demand for radio communications raises the need to optimize the performance while maximizing the capacity of wireless communications systems. What is needed is an efficient signal processing technique to improve the quality and spectral efficiency of wireless communications and better techniques for sharing the limited bandwidth among different high capacity users. As can be seen, attempts to make real-time processing multi-user processing have been frustrated by complex and sophisticated hardware and processing requirements.